package com.gxc.array;

/**
 * 给定一个N*N的矩阵matrix，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
 * 例如:
 * 01111
 * 01001
 * 01001
 * 01111
 * 01011
 * 其中边框全是1的最大正方形的大小为4*4，所以返回4。
 */
public class MaxSquare {

    public static void main(String[] args) {
        int[][] matrix = bulidMatrix();

        int maxSize = getMaxSquareSize(matrix);
        System.out.println(maxSize);

        System.out.println("----方法2---");
        maxSize = getMaxSquareSize2(matrix);
        System.out.println(maxSize);
    }

    /**
     * 时间复杂度n的三次方，但是如果有大于1长度的正方形，则不需要遍历所有点
     * @param matrix
     * @return
     */
    private static int getMaxSquareSize2(int[][] matrix) {
        int[][] right = new int[matrix.length][matrix[0].length];
        int[][] below = new int[matrix.length][matrix[0].length];

        initRightAndBelow(matrix, right, below);
        for (int i = 0; i < right.length; i++) {
            for (int j = 0; j < right[i].length; j++) {
                System.out.print(right[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("----");
        for (int i = 0; i < below.length; i++) {
            for (int j = 0; j < below[i].length; j++) {
                System.out.print(below[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("-----");

        //按照最大边长遍历
        for (int length = Math.min(matrix.length, matrix[0].length); length > 0; length--) {
            if (hasSquare(length, right, below)) {
                return length;
            }
        }

        return 0;
    }

    /**
     * 是否有length长度的正方形
     * @param length
     * @param right
     * @param below
     * @return
     */
    private static boolean hasSquare(int length, int[][] right, int[][] below) {
        for (int row = 0; row+length <= right.length; row++) {
            for (int col = 0; col+length <= right[row].length; col++) {
                //row col 左上角 右侧有length个连续的1，下方有length个连续的1
                //row+length-1 col 左下角 右侧有length个连续的1
                //row col+length-1 右上角 下方有length个连续的1
                if (right[row][col] >= length &&
                        right[row+length-1][col]>=length &&
                        below[row][col]>=length &&
                        below[row][col+length-1]>=length) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 初始化预处理矩
     * @param matrix
     * @param right i点本身和右侧有多少个连续的1
     * @param below i点本身和下方有多少个连续的1
     */
    private static void initRightAndBelow(int[][] matrix, int[][] right, int[][] below) {
        //最后一列
        int lastCol = matrix[0].length-1;
        //最后一行
        int lastRow = matrix.length-1;

        right[lastRow][lastCol] = matrix[lastRow][lastCol];
        below[lastRow][lastCol] = matrix[lastRow][lastCol];
        //初始化最后一列
        for (int row = lastRow-1; row >=0; row--) {
            if (matrix[row][lastCol] == 1) {
                right[row][lastCol] = 1;
                below[row][lastCol] = below[row+1][lastCol]+1;
            }
        }
        //初始化最后一行
        for (int col = lastCol-1; col>=0; col--) {
            if (matrix[lastRow][col] == 1) {
                below[lastRow][col] = 1;
                right[lastRow][col] = right[lastRow][col+1]+1;
            }
        }
        //其他位置从右向左，从下往上
        for (int row = matrix.length - 2; row >= 0; row--) {
            for (int col = matrix[row].length - 2; col >= 0; col--) {
                if (matrix[row][col] == 1) {
                    below[row][col] = below[row+1][col]+1;
                    right[row][col] = right[row][col+1]+1;
                }
            }
        }
    }

    /**
     * 时间复杂度，n的平方
     * @param matrix
     * @return
     */
    public static int getMaxSquareSize(int[][] matrix) {
        int[][] right = oneInARowOnTheRight(matrix);
        int[][] below = oneInARowBelow(matrix);

        for (int i = 0; i < right.length; i++) {
            for (int j = 0; j < right[i].length; j++) {
                System.out.print(right[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("----");
        for (int i = 0; i < below.length; i++) {
            for (int j = 0; j < below[i].length; j++) {
                System.out.print(below[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("-----");
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (right[i][j] != 0 && below[i][j]!=0) {
                    //比较i点最大的连续1值，最小的连续i值就是可能的正方形的边长
                    int min = Math.min(right[i][j], below[i][j]);
                    if (i+min-1<=matrix.length-1 && j+min-1<=matrix[0].length-1) {
                        if (right[i+min-1][j]>=min && below[i][j+min-1]>=min) {
                            max = Math.max(max, min);
                        }
                    }
                }
            }
        }
        return max;
    }

    /**
     * i点右侧有多少个连续的1
     * @param matrix
     * @return
     */
    private static int[][] oneInARowOnTheRight(int[][] matrix) {
        int[][] right = new int[matrix.length][matrix[0].length];
        for (int row = 0; row < matrix.length; row++) {
            for (int col = matrix[row].length - 1; col >= 0; col--) {
                if (matrix[row][col] == 1) {
                    if (col == matrix[row].length-1) {
                        right[row][col] = 1;
                    } else {
                        right[row][col] = right[row][col+1] +1;
                    }
                }
            }
        }
        return right;
    }

    /**
     * i点下方有多少个连续的1
     * @param matrix
     * @return
     */
    private static int[][] oneInARowBelow(int[][] matrix) {
        int[][] below = new int[matrix.length][matrix[0].length];
        int col = matrix[0].length;
        for (int i = col -1; i >= 0; i--) {
            int row = matrix.length;
            for (int j = row-1; j >= 0; j--) {
                if (matrix[j][i] == 1) {
                    if (j == row-1) {
                        below[j][i] = 1;
                    } else {
                        below[j][i] = below[j+1][i] + 1;
                    }
                }
            }
        }
        return below;
    }


    private static int[][] bulidMatrix() {
        int[][] matrix = new int[5][5];
        matrix[0][0] = 0;
        matrix[0][1] = 1;
        matrix[0][2] = 1;
        matrix[0][3] = 1;
        matrix[0][4] = 1;

        matrix[1][0] = 0;
        matrix[1][1] = 1;
        matrix[1][2] = 0;
        matrix[1][3] = 0;
        matrix[1][4] = 1;

        matrix[2][0] = 0;
        matrix[2][1] = 1;
        matrix[2][2] = 0;
        matrix[2][3] = 0;
        matrix[2][4] = 1;

        matrix[3][0] = 0;
        matrix[3][1] = 1;
        matrix[3][2] = 1;
        matrix[3][3] = 1;
        matrix[3][4] = 1;

        matrix[4][0] = 0;
        matrix[4][1] = 1;
        matrix[4][2] = 0;
        matrix[4][3] = 1;
        matrix[4][4] = 1;
        return matrix;
    }
}
